"""
用回溯法解决旅行商问题。
"""

from tsp_common_code import read_graph, AdjacencyMatrix
from typing import List, Optional


class BacktrackingSolution:
    graph: AdjacencyMatrix
    visited: List[bool]
    route: List[int]
    best_dist: Optional[int]
    best_route: List[int]

    def __init__(self, graph: AdjacencyMatrix):
        self.graph = graph

    def dfs(self, *, count: int, dist: int) -> None:
        city_num = len(self.graph)
        currently_in = self.route[-1]

        if self.best_dist is not None and dist >= self.best_dist:
            # 剪枝：如果当前总长度已经超过最优长度，那么当前路线不可能是最优解
            return

        if count == city_num:
            # 走到了最后一个城市，更新答案
            total_dist = dist + self.graph[currently_in][0]
            if self.best_dist is None or total_dist < self.best_dist:
                self.best_dist = total_dist
                self.best_route = self.route + [0]
                print(f'找到一条新路线：{self.best_route}，总长度为 {self.best_dist}')

            return

        for i in range(city_num):
            if self.visited[i]:
                continue

            # 从当前城市前往 i 城市
            self.visited[i] = True
            self.route.append(i)
            self.dfs(
                count=count + 1,
                dist=dist + self.graph[currently_in][i],
            )
            self.route.pop()
            self.visited[i] = False

    def solve(self) -> None:
        self.visited = [False] * len(self.graph)
        self.visited[0] = True
        self.route = [0]
        self.best_dist = None

        self.dfs(count=1, dist=0)


def main():
    graph = read_graph()
    if len(graph) <= 1:
        result_dist, result_route = 0, []
    else:
        solution = BacktrackingSolution(graph)
        solution.solve()
        result_dist, result_route = solution.best_dist, solution.best_route

    print(f'\n最佳路线：{result_route}\n最佳路线总长度：{result_dist}\n')


if __name__ == '__main__':
    main()
